Vertex Partitions into an Independent Set and a Forest with Each Component Small

Abstract: For each integer $k \ge 2$, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and $F_k$, where I is an independent set and $G[F_k]$ is a forest in which each component has at most $k$ vertices. For each $k$ we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G) < g(a,b) then V(G) has a partition into sets A and B such that mad(G[A]) < a and mad(G[B]) < b. They specifically asked for the value of g(1,b), which corresponds to the case that A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find the value of g(1,b) whenever 4/3 < b < 2. This is joint work with Matthew Yancey.

combinatorics

Audience: researchers in the topic

Comments: password 061801

SCMS Combinatorics Seminar

Series comments: Check scmscomb.github.io/ for more information